package lec19graph.part0traversal;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

//DAG （Directed acyclic graph）有向无环图的拓扑排序
public class GraphTopSort {
    final static int INF = Integer.MAX_VALUE >> 1;
    static int n = 5;
    static int[] book = new int[n];
    static int[][] g = new int[][]{
            {0, 1, 1, INF, INF},//A->B A->C
            {INF, 0, INF, 1, INF},//B->D
            {INF, 1, 0, INF, 1},//C->B C->E
            {INF, INF, INF, INF, INF},//
            {INF, INF, INF, INF, INF}

    };
    static int[] du = new int[n];//每一个点的入度数组


    public static void main(String[] args) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1)
                    ++du[j];
            }
        }
        System.err.println(Arrays.toString(du));
        System.out.println(topologicalSort());
    }

    private static boolean topologicalSort() {

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (du[i] == 0 && book[i] == 0) {
                q.add(i);
                book[i] = 1;

            }
        }
        int sum = 0;
        while (true) {
            if (q.isEmpty()) break;
            int h = q.poll();
            ++sum;
            System.out.println((char) ('A' + h));
            for (int i = 0; i < n; i++)
                if (g[h][i] == 1) {
                    --du[i];
                    if (du[i] == 0) {
                        q.add(i);
                        book[i] = 1;
                    }
                }

        }
        return sum == n;


    }


}
